import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/*
* 算法：遍历
*
  1. 将所有节点放入数组
  2. 看数组中是否有两数和同给定值相等

  分析：
  没有用到任何二叉搜索树的特性，空间、时间都不是最优，较为浪费
* */
public class Solution_1 {
    public boolean findTarget(TreeNode root, int k) {
        List<Integer> list = treeToArray(root,new ArrayList<>());
        System.out.println(list);
        return isTwoSum(list,k);

    }

    //两数之和，判断数组中，是否存在两个数之和跟target值相等
    public boolean isTwoSum(List<Integer> sums,int target){
        Set<Integer> set = new HashSet<>();
        for(int i=0;i<sums.size();i++){
            if(set.contains(target-sums.get(i)))
            {
                return true;
            }
            set.add(sums.get(i));
        }
        return false;
    }

    //遍历二叉树
    public List<Integer> treeToArray(TreeNode node,List<Integer> list)
    {
        if(node!=null)
            list.add(node.val);
        if(node.left!=null)
            treeToArray(node.left,list);
        if(node.right!=null)
            treeToArray(node.right,list);
        return list;
    }

}
